#include<iostream>
#include <bits/stdc++.h>
#include <vector>

#include <typeinfo>

using namespace std;

void quickSort(vector<int>& nums, int start, int end) {
    int left = start;
    int right = end;
    int p = left;

    if (end < start) return;

    auto swap = [&nums](int l, int r) {
        int t = nums[l];
        nums[l] = nums[r];
        nums[r] = t;
    };

    cout << typeid(nums).name() << endl;

    while(left < right) {
        while(left < right && nums[right] >= nums[p]) {
            --right;
        }
        while(left < right && nums[left] <= nums[p]) {
            ++left;
        }
        
        swap(left, right);
    }
    swap(left, p);

    quickSort(nums, start, left - 1);
    quickSort(nums, left + 1, end);
}

int main() {
    vector<int> nums = {1,3,3,4,6,2,33,7,9,0,-1};
    quickSort(nums, 0, nums.size() - 1);
    for(size_t i = 0; i < nums.size(); ++i) {
        std::cout << nums[i] << std::endl;
    }

    std::cout << "Hello World!" << std::endl;
    return 0;
}